package two.chapter_4.c4_2;

import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.In;

/**
 * 有向图
 */
public class Digragh {
    private Bag<Integer>[] adj;
    private int v;
    private int e;

    public Digragh(int v) {
        this.v = v;
        this.e=0;
        adj = new Bag[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new Bag<>();
        }

    }

    public Digragh(In in) {
        this(in.readInt());
        int e = in.readInt();
        for (int i = 0; i < e; i++) {
            int v = in.readInt();
            int w = in.readInt();
            addEdge(v,w);
        }
    }

    /**
     * 向有向图中添加一条边v-> w
     *
     * @param v
     * @param w
     */
    public  void addEdge(int v, int w){
        adj[v].add(w);
        e++;
    }

    /**
     * 总顶点数
     *
     * @return
     */
    public int v() {
        return v;
    }

    /**
     * 总边数
     *
     * @return
     */
    public int e() {
        return e;
    }

    /**
     * 由v指出的边所连接的所有顶点
     *
     * @param v
     * @return
     */
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    /**
     * 该图的反向图
     *
     * @return
     */
    public Digragh reverse() {
        Digragh r=new Digragh(v);
        for (int i=0;i<v;i++){
            for (int w:adj[i]){
                r.addEdge(w,i);
            }
        }
        return r;
    }

    @Override
    public String toString() {
        String s=v+" vertices, "+e+" edges\n";
        for (int i=0;i<v;i++){
            s+=i+"：";
            for (int w:this.adj(i)){
                s+=w+" ";
            }
            s+="\n";
        }
        return s;
    }
}
